When a table or index needs more space in a database,
SQL Server needs a way to determine where space is available in the
database to be allocated. If the table or index is still fewer than
eight pages in size, SQL Server must find a mixed extent with one or
more pages available that can be allocated. If the table or index is
eight pages or larger in size, SQL Server must find a free uniform
extent that can be allocated to the table or index.
Extents
If SQL Server allocated space one page at a time as
pages were needed for a table (or an index), SQL Server would be
spending a good portion of its time just allocating pages, and the data
would likely be scattered noncontiguously throughout the database.
Scanning such a table would not be very efficient. For these reasons,
pages for each object are grouped together and allocated in extents; an extent consists of eight logically contiguous pages.
When a table or index is created, it is initially
allocated a page on a mixed extent. If no mixed extents are available in
the database, a new mixed extent is allocated. A mixed extent can be
shared by up to eight objects (each page in the extent can be assigned
to a different table or index).
As the table grows to at least eight pages in size, all future allocations to the table are done as uniform extents.
Figure 1 shows the use of mixed and uniform extents.
If
SQL Server had to search throughout an entire database file to find
free extents, it wouldn’t be efficient. Instead, SQL Server uses two
special types of pages to record which extents have been allocated to
tables or indexes and whether it is a mixed or uniform extent:
Global and Shared Global Allocation Map Pages
The allocation map pages track whether extents have
been allocated to objects and indexes and whether the allocation is for
mixed extents or uniform extents. As mentioned in the preceding section,
there are two types of GAMs:
Global allocation map (GAM)—
The GAM keeps track of all allocated extents in a database, regardless
of what it’s allocated to. The structure of the GAM is straightforward:
each bit in the page outside the page header represents one extent in
the file, where 1 means that the extent is not allocated, and 0
means that the extent is allocated. Nearly 8,000 bytes (64,000 bits)
are available in a GAM page after the header and other overhead bytes
are taken into account. Therefore, a single GAM covers approximately
64,000 extents, or 4GB (64,000 * 64KB) of data.
Shared global allocation map (SGAM)—
The SGAM keeps track of mixed extents that have free space available.
An SGAM has a structure similar to a GAM, with each bit representing an
extent. A value of 1 means that the extent is a mixed extent and there is free space (at least one unused page) available on the extent. A value of 0
means that the extent is not currently allocated, that the extent is a
uniform extent, or that the extent is a mixed extent with no free pages.
Table 1 summarizes the meaning of the bit in GAMs and SGAMs.
Table 1. Meaning of the GAM and SGAM Bits
Extent Usage | GAM Bit | SGAM Bit |
---|
Free, not used | 1 | 0 |
Uniform or mixed with no free pages | 0 | 0 |
Mixed, with free pages available | 0 | 1 |
When SQL Server needs to allocate a uniform extent, it simply searches the GAM for a bit with a value of 1 and sets it to 0 to indicate it has been allocated. To find a mixed extent with free pages, it searches the SGAM for a bit set to 1. When all pages in a mixed extent are used, its corresponding bit is set to 0. When a mixed extent needs to be allocated, SQL Server searches the GAM for an extent whose bit set to 1 and sets the bit to 0, and the corresponding SGAM bit is set to 1.
There is some more processing involved as well, such as spreading the
data evenly across database files, but the allocation algorithms are
still relatively simple.
SQL
Server is able to easily locate GAM pages in a database because the
first GAM page is located at the third page in the file (page number 2).
There is another GAM every 511,230 pages after the first GAM. The
fourth page (page number 3) in each database file is the SGAM page, and
there is another SGAM each 511,230 pages after the first SGAM.
Page Free Space Pages
A page free space (PFS)
page records whether each page is allocated and the amount of free
space available on the page. Each PFS covers 8,088 contiguous pages in
the file. For each of the 8,088 pages, the PFS has a 1-byte record that
contains a bitmap for each page indicating whether the page is empty, 1
to 50% full, 51 to 80% full, 81 to 95% full, or more than 95% full. The
first PFS page in a file is located at page number 1, the second PFS
page is located at page 8088, and each additional PFS page is located
every 8,088 pages after that. SQL Server uses PFS pages to find free
pages on extents and to find pages with space available on extents when a
new row needs to be added to a table or index.
Figure 2
shows the layout of GAM, SGAM, and PFS pages in a database file. Note
that every file has a single file header located at page 0.
Index Allocation Map Pages
Index allocation map (IAM)
pages keep track of the extents used by a heap or index. Each heap
table and index has at least one IAM page for each file where it has
extents. An IAM cannot reference pages in other database files; if the
heap or index spreads to a new database file, a new IAM for the heap or
index is created in that file. IAM pages are allocated as needed and are
spread randomly throughout the database files.
An IAM page contains a small header that has the
address of the first extent in the range of pages being mapped by the
IAM. It also contains eight page pointers that keep track of index or
heap pages that are in mixed extents. These pointers might or might not
contain any information, depending on whether any data has been deleted
from the tables and the page(s) released. Remember, an index or heap
will have no more than eight pages in mixed extents (after eight pages,
it begins using uniform extents), so only the first IAM page stores this
information. The remainder of the IAM page is for the allocation
bitmap. The IAM bitmap works similarly to the GAM, indicating which
extents over the range of extents covered by the IAM are used by the
heap or index the IAM belongs to. If a bit is on, the corresponding
extent is allocated to the table.
Each IAM covers a possible range of 63,903 extents (511,224 pages), covering a 4GB section of a file. Each bit represents an extent within that range, whether or not the extent is allocated to the object that the IAM belongs to. If the bit is set to 1, the relative extent in the range is allocated to the index or heap. If the bit is set to 0, the extent is either not allocated or might be allocated to another heap or index.
For example, assume that an IAM page resides at page 649 in the file. If the bit pattern in the first byte of the IAM is 1010 0100,
the first, third, and sixth extents within the range of the IAM are
allocated to the heap or index. The second, fourth, fifth, seventh, and
eighth extents are not.
Note
For a heap table, the data pages and rows within them
are not stored in any specific order. Unlike versions of SQL Server
prior to 7.0, the pages in a heap structure are not linked together in a
page chain. The only logical connection between data pages is the
information recorded in the IAM pages, which are linked together.
Differential Changed Map Pages
The seventh page (page number 6), and every 511,232nd page thereafter, in the database file is the differential changed map (DCM)
page. This page keeps track of which extents in a file have been
modified since the last full database backup. When an extent has been
modified, its corresponding bit in the DCM is turned on. This
information is used when a differential backup is performed on the
database. A differential backup copies only the extents changed since
the last full backup was made. Using the DCM, SQL Server can quickly
tell which extents need to be backed up by examining the bits on the DCM
pages for each data file in the database. When a full backup is
performed for the database, all the bits are set back to 0.
Bulk Changed Map Pages
The eighth page (page number 7), and every 511,232nd page thereafter, in the database file is the bulk changed map (BCM). When you perform a minimally or bulk-logged operation in SQL Server 2008 in BULK_LOGGED
recovery mode, SQL Server logs only the fact that the operation
occurred and doesn’t log the actual data changes. The operation is still
fully recoverable because SQL Server keeps track of what extents were
actually modified by the bulk operation in the BCM page. Similar to the
DCM page, each bit on a BCM page represents an extent within its range,
and if the bit is set to 1, that indicates that the
corresponding extent has been changed by a minimally logged bulk
operation since the last full database backup. All the bits on the BCM
page are reset to 0 whenever a full database backup or log backup occurs.
When you initiate a log backup for a database using the BULK_LOGGED
recovery model, SQL Server scans the BCM pages and backs up all the
modified extents along with the contents of the transaction log itself.
You should be aware that the log file itself might be small, but the
backup of the log can be many times larger if a large bulk operation has
been performed since the last log backup.